package com.xzz.dp;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author: hhz
 * @create: 2021-12-31 15:13
 * 354. 俄罗斯套娃信封问题
 * 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
 *
 * 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
 *
 * 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
 *
 * 注意：不允许旋转信封。
 *
 * 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
 * 输出：3
 * 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
 *
 **/
public class MaxEnvelopes {
    public static void main(String[] args) {
        System.out.println(maxEnvelopes(new int[][]{new int[]{5,4},new int[]{6,4},new int[]{6,7},new int[]{2,3}}));
    }
    public static int maxEnvelopes(int[][] envelopes) {
        PriorityQueue<int[]> minQueue = new PriorityQueue<>((nums1,nums2)->{
            if(nums1[0] ==nums2[0]){
                return nums2[1]-nums1[1];
            }else {
                return nums1[0]-nums2[0];
            }
        });
        for (int i = 0; i < envelopes.length; i++) {
            minQueue.offer(envelopes[i]);
        }
        int[] nums = new int[envelopes.length];
        int i = 0;
        while (!minQueue.isEmpty()){
            nums[i] = minQueue.poll()[1];
            i++;
        }
        return longestPalindromeSubseq(nums);
    }
    //最长递增子序列
    public static int longestPalindromeSubseq(int[] nums ) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        for (int i = 0; i <nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j]<nums[i]){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(dp[i],res);
        }
        return res;

    }
}
